# class Solution(object):
#     def findKthLargest(self, nums, k):
#         """
#         :type nums: List[int]
#         :type k: int
#         :rtype: int
#         """
#         nums.sort(reverse=True)
#         return nums[k - 1]
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        n = len(nums)

        def swap(i, j):
            temp = nums[i]
            nums[i] = nums[j]
            nums[j] = temp

        def adjudge_heap(i):
            left = 2 * i + 1
            right = 2 * i + 2
            largest = i
            if left < n and nums[left] > nums[largest]:
                largest = left
            if right < n and nums[right] > nums[largest]:
                largest = right
            if largest != i:
                swap(largest, i)
                adjudge_heap(largest)

        for i in range(n // 2 - 1, -1, -1):
            adjudge_heap(i)
        print(nums)
        for i in range(k):
            if i == k - 1:
                return nums[0]
            else:
                nums[0] = nums.pop()
                n -= 1
                adjudge_heap(0)



data = Solution()
nums = [1]
k = 1
print(data.findKthLargest(nums, k))
